#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define maxn 100010
#define sqrtN  316    // int(sqrt(100010)),表示块内元素个数
int block[sqrtN];      //记录每一块中存在的元素个数
int table[maxn];       // hash数组，记录元素当前存在个数
/*堆栈的定义*/
typedef int ElementType;
//堆栈的定义 
typedef int Position;   //栈顶位置
typedef struct SNode* PtrToSNode;
struct SNode {
    ElementType *Data;
    Position Top;
    int MaxSize;
};
typedef PtrToSNode Stack;
/*堆的建立*/
Stack CreateStack(int MaxSize) {
    Stack S =(Stack) malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize*sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}
int n=0;//栈中元素个数 
void peekMedian(int k) {//取中值函数
    int sum = 0, idx = 0; //当前累积存在的数的个数，块号
    while (sum + block[idx] < k) {
        sum += block[idx++]; //未达到k，则累加上当前块的元素个数
    }
    int num = idx * sqrtN; // idx号块的第一个数
    while (sum + table[num] < k) {
        sum += table[num++]; //继续累加，直到k
    }
    printf("%d\n", num);
}
bool IsEmpty(Stack S) {
    return(S->Top==-1);
}
void Push(Stack S,ElementType x) {
    S->Data[++S->Top]=x;
    block[x / sqrtN]++; // x所在块的元素个数+1
    table[x]++; // x个数+1 
	n++;//栈中元素个数 
}

void Pop(Stack S) {
    int x=S->Data[(S->Top)--];
    block[x / sqrtN]--; // x所在块的元素个数-1
    table[x]--;         // x个数-1
    printf("%d\n", x);
    n--;//栈中元素个数 
}

int main() {
    int x, q;
	char c[11];
    scanf("%d", &q);
    Stack S=CreateStack(q);	
    for (int i = 0; i < q; i++) {
        scanf("%s",c);
        if (c[1] == 'o') {//如果字符串是pop
          if (IsEmpty(S)) {
                printf("Invalid\n");//栈为空的情况
            } else {
                Pop(S);
            } 
        } else if (c[1] == 'u') {//如果字符串是push    
            scanf("%d", &x);//输入要push的数字
            Push(S,x);
        } else {
            if (IsEmpty(S)) {
                printf("Invalid\n");//栈为空的情况
            } else {
                int k =n ;//栈的大小 
                if (n% 2 == 1) //如果栈的数目为奇数 
                    k = (k + 1) / 2;
                else//栈的数目为偶数 
                    k /= 2;
                peekMedian(k);//位于栈中间的数; 
            }
        }
    }
    return 0;
}